It seems strange, but
mushrooms like soda. Moreover, Michael likes to make experiments with it. Each
kind of soda has it's own level of sweetness. Michael
has n containers with soda of different levels. If Michael mix two
containers with levels x and y, instead of these two he will get
soda with level 2 * min(x, y).
Help Michael to get soda
with the highest possible level of sweetness.
Input. The first line contains the
number of containers n (1
≤ n ≤ 106). The second line
contains n integers: the level of sweetness xi (-109
≤ xi ≤ 109).
Output. Print the highest possible
level of sweetness that can be obtained by mixing some of the available sodas.
|
Sample input |
Sample output |
|
3 1 3 6 |
6 |
greedy
Add all
containers to the multiset (containers with the same sweetness level may appear
during the mixing process). It makes sense to mix water with sweets x and y
if the level of resulting sweetness is
reater than max(x, y).
Consider two
waters with the lowest levels of sweetness x
and y.
·
If 2x
≤ y, then after mixing them you
get water with a level of sweetness 2 * min(x, y)
= 2x, which is not more than y. In this case, there is no point in mixing: we will remove
the sweetness x from the
multiset and the corresponding capacity will not be considered further.
·
If 2x > y, then after mixing them you get water with a level of sweetness 2 * min(x, y) = 2x, which is more than y. Remove
x and y sweets from the multiset and add sweets 2x.
Perform the
described operation with the two smallest sweets x and y while the
multiset contains more than one element.
Declare a multiset.
multiset<long
long> m;
Read the number
of containers n. Add the levels of
sweets of the given
containers to the multiset.
scanf("%d",&n);
for(i
= 0; i < n; i++)
{
scanf("%lld",&val);
m.insert(val);
}
Process
the multiset while it contains more than one element.
while(m.size()
> 1)
{
Extract the two smallest sweets a and b.
long long a = *m.begin(); m.erase(m.begin());
long long b = *m.begin();
If mixing them produces a sweetness greater than max(a, b),
then mix and add the resulting sweetness 2a to the multiset.
Otherwise, remove sweetness a from
the multiset, and leave sweetness b.
if (2 * a
> b)
{
m.erase(m.begin());
m.insert(2*a);
}
}
Print the
answer – the maximum
possible level of sweetness.
printf("%lld\n",*m.begin());